%\documentclass[a4paper]{article}
%\usepackage[spanish]{babel}
%\usepackage[utf8]{inputenc}
%\usepackage[hmargin=1cm]{geometry}
%\usepackage{graphicx}
%\usepackage{subfigure}
%\usepackage{amsmath}

	\section{Problema 2: Replicación de contenido}

	\subsection{Introducción}

		Una organización debe implementar una solución de replicación (o sincronización) de contenido para su red de entrega de contenidos en Internet.
		Para ello dispone de $n$ servidores interconectados mediante $m$ enlaces \emph{backbone} de alta velocidad.
		Uno de los servidores actuará como \emph{master} y será el primero en recibir la información a replicar.
		Desde allí será enviada a otros servidores utilizando los enlaces \emph{backbone}.
		La utilización de los enlaces tiene un costo en función del tráfico que transmiten.
		Cada servidor recibirá la información, guardara una copia local y la retransmitirá a los demás servidores.
		Este proceso, llamado \emph{broadcast}, se repite hasta que los $n$ servidores contengan la nueva información.

		La organización desea minimizar el costo de la transmisión y el tiempo de replicación.
		Para ello encargó el trabajo de optimización a dos consultoras.

		La primera consultora debe elegir los enlaces a utilizar de manera que la información pueda distribuirse a todos los servidores con un costo mínimo.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{example1}}
			\caption{Enlaces de menor costo seleccionados para resolver el problema (rojo).}
			\label{fig:example1}
		\end{figure}

		En la figura~\ref{fig:example1}, se puede observar que la forma menos costosa de replicar el mensaje a todos los servidores es seleccionando el conjunto de aristas $V' = \{(1,2), (1,4), (2,3), (2,5)\}$.

		La segunda consultora debe elegir un servidor como \emph{master} de forma tal que el proceso de replicación termine en el menor tiempo posible.
		Se supone que la información tarda lo mismo en atravezar cualquier enlace.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{example2}}
			\caption{Elección servidor maestro (rojo).}
			\label{fig:example2}
		\end{figure}

		El la figura~\ref{fig:example2} se puede observar que el servidor representado por el vértice $2$, es la mejor elección como servidor maestro.
		El mensaje llegará a los demás servidores ($S'=\{1,3,4,5\}$) al mismo tiempo, minimizando el tiempo de transmisión.

		\subsection{Optimizando el costo de replicación}

		Lo que tratamos de lograr es minimizar el costo de replicación.
		Para ello debemos ser capaces de utilizar la mínima cantidad de enlaces y de menor costo, para replicar el mensaje.

		Pensemos los servidores como vértices y los enlaces que los conectan como aristas.
		Lo que queremos buscar es un subgrafo del mismo con las siguientes características:

		\begin{enumerate}
			\item
			Que contenga a todos los vértices del grafo.
			Dicho de otra forma, todos los servidores deben recibir el mensaje.

			\item
			Ser conexo.
			Caso contrario el mensaje no podría ser transmitido a los demás servidores.
			Cada servidor debe poder ser alcanzable desde cualquier otro.

			\item
			No tener circuitos simples.
			No es necesario tener más de un camino simple para ir de un vértice a otro (de un servidor a otro).
			De tenerlos agregaría costo a la solución.

			\begin{figure}[!ht]
				\centering
				\subfigure[]{
					\includegraphics[scale=0.5]{example3}
					\label{fig:example3}
				}
				\subfigure[]{
					\includegraphics[scale=0.5]{example3a}
					\label{fig:example3a}
				}
				\subfigure[]{
					\includegraphics[scale=0.5]{example3b}
					\label{fig:example3b}
				}
				\caption{Basta con utilizar las aristas en rojo, figuras \subref{fig:example3a} y \subref{fig:example3b}, para transmitir el mensaje a todos los servidores.}
				\label{fig:example3all}
			\end{figure}

			Como se aprecia en la figura~\ref{fig:example3all}, si utilizamos todas las aristas del grafo representado en la figura~\ref{fig:example3} agregamos un costo inecesario.

			\item
			Que la suma de los costos de las aristas (enlaces) sea la menor posible.

		\end{enumerate}

		De los puntos 2 y 3 deducimos que se trata de un árbol.
		Si agregamos el punto 1, podemos decir que estamos buscando en particular un \emph{árbol generador} del grafo.
		Finalmente del punto 4 que es de mínimo valor en cuanto a la suma de los pesos de las aristas, es decir un \emph{árbol generador mínimo}.

		Los algoritmos más usuales para resolver el problema son los de \emph{Kruskal} y \emph{Prim}\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capítulo 6: Graph Algoritm's, Sección 23.2: The algoritms of Kruskal and Prim}.
		El elegido en este trabajo fue el \emph{algoritmo de Kruskal}.
		La elección se debe a que posee ciertas ventajas a la hora de implementarlo en contrariedad a \emph{Prim}.
		\emph{Kruskal} es de más fácil implementación y permite la introducción de una estructura llamada \emph{disjoint-set}\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capítulo 5: Advanced Data Structures, Sección 21: Data Structures for Disjoint Sets}.
		La estructura \emph{disjoint-set} reduce la cota temporal del algortimo al incorporarle dos heurísticas: \emph{union-by-rank} y \emph{path-compression}.

		Para formar el \emph{árbol generador mínimo}, se parte de un subgrafo que posee todos los nodos del grafo aislados.
		Cada nodo del subgrafo forma una componente conexa distinta.
		Las aristas de menor peso del grafo se van incorporando al subgrafo de forma tal que no se formen ciclos.
		Debido a la condición anterior sólo se pueden unir vértices pertenecientes a componentes conexas distintas.
		El subgrafo que estamos formando es acíclico y por ende un bosque.
		Cada componente conexa que le forma es un árbol, luego añadir una arista que una vértices de la misma componente conexa es añadir una arista a un árbol con lo cuál se formaría un ciclo (ver figura~\ref{fig:proposicion1}).
		
		\begin{figure}[!ht]
			 Las siguientes condiciones sobre un grafo $G=(V,E)$ son equivalentes.
			\begin{enumerate}
				\item
				$G=(V,E)$ es árbol.
				\item
				$G=(V,E)$ es conexo, y para cada $e \in E$, se tiene que $G_1=(V,E-\{e\})$ no es conexo.
				\item
				$G$ es acíclico y para cada $e \notin E$, se tiene que $G_1=(V,E\cup\{e\})$ no es acíclico.
			\end{enumerate}

			\caption{\textbf{Proposición 1}}
			\label{fig:proposicion1}
		\end{figure}

		El algoritmo de Kruskal (figura~\ref{fig:kruskal}) replica el concepto descripto arriba para construir un árbol generador mínimo.
		Cada componente componente conexa se representa con un conjunto de nodos en el \emph{disjoint-set}.
		La idea es incorporar las aristas $(x,y)$ donde $x$ e $y$ pertenezcan a diferentes conjuntos, o dicho de otra forma a distintas componentes conexas.

		\begin{figure}[!ht]
			\begin{enumerate}
				\item
				Se ordenan las aristas de menor a mayor costo.

				\item
				Se crea un \emph{disjoint-set} con tantos conjuntos como nodos.

				\item
				Por cada arista $(x,y)$
				\begin{enumerate}
					\item
					Se busca el conjunto al cual pertenecen los vértices $x$ e $y$.

					\item
					Si los vértices $x$ e $y$ pertenecen al mismo conjunto (componente conexa), entonces se trata de una arista que forma un ciclo.
					Por lo tanto se descarta.

					\item
					Si los vértices $x$ e $y$ pertenecen a conjuntos distintos, se unen los conjuntos.
					Se agrega $(x,y)$ a la solución.
				\end{enumerate}

			\end{enumerate}

			\caption{\textbf{Algortimo de Kruskal}}
			\label{fig:kruskal}
		\end{figure}

	\subsubsection{Disjoint sets}

		La estructura \emph{disjoint-set} sirve para realizar un seguimiento de un conjunto de elementos particionados en una serie de subconjuntos disjuntos.

		Los conjuntos del \emph{Disjoint-set} se representan por medio de un arreglo.
		Cada posición del arreglo representa un elemento del conjunto (en este caso un vértice) que contiene un puntero (índice) a un elemento padre.
		De esta forma nos queda una estructura tipo árbol, el conjunto, en donde la raíz (el elemento que no tiene padre) identifica al mismo.
		Para buscar el conjunto al que pertenece un elemento debemos seguir los enlaces hacia la raíz.
		Al principio cada vértice del grafo forma un conjunto en dónde es el único elemento existente.
		Cada conjunto representa una componente conexa del subgrafo que se está formando.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-graph0}}
			\caption{Grafo con pesos en sus aristas.}
			\label{fig:disjointgraph0}
		\end{figure}

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-1}}
			\caption{\emph{Disjoint-set}, estado inicial. Representando la figura~\ref{fig:disjointgraph0}}
			\label{fig:disjoint1}
		\end{figure}

		\newpage
		
		Tomemos una de las aristas de menor peso, $(1,4)$.
		Debemos buscar los conjuntos a los que pertenecen los vértices $1$ y $4$.
		El vértice $1$ pertenece a el conjunto $1$ y el vértice $4$ al conjunto $4$, por ser $1$ y $4$ raíces de los árboles que representan sus conjuntos.
		Unimos los conjuntos asignando como padre del vértice $1$ al $4$, figura~\ref{fig:disjoint2}(o viceversa, digamos que es lo mismo sólo por ahora).

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-2}}
			\caption{\emph{Disjoint-set}, union de los conjuntos $1$ y $4$.}
			\label{fig:disjoint2}
		\end{figure}

		Ahora $1$ y $4$ se encuentran en el mismo conjunto (representado por su raíz el $4$), o sea en la misma componente conexa.
		Volviendo a repetir el proceso con la arista $(2,3)$ resulta lo observable en la figura~\ref{fig:disjoint3}.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-3}}
			\caption{\emph{Disjoint-set}, union de los conjuntos $2$ y $3$.}
			\label{fig:disjoint3}
		\end{figure}

		Sigamos con la arista $(4,5)$.
		Si buscamos $4$ y $5$ en el \emph{Disjoint-set} nos encontramos con que pertenecen a los conjuntos $4$ y $5$ respectivamente.
		Los unimos resultando la figura~\ref{fig:disjoint4}.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-4}}
			\caption{\emph{Disjoint-set}, union de los conjuntos $4$ y $5$.}
			\label{fig:disjoint4}
		\end{figure}

		\newpage

		A continuación agreguemos la arista $(1,2)$.
		El vértice $1$ se encuentra en el conjunto $5$ y el $2$ en el conjunto $3$.
		Si unimos los conjuntos $5$ y $2$ nos queda la figura~\ref{fig:disjoint5}.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-5}}
			\caption{\emph{Disjoint-set}, union de los conjuntos $3$ y $5$.}
			\label{fig:disjoint5}
		\end{figure}

		Finalmente todos los nodos se encuentran en la misma componente conexa formando un sólo conjunto.
		Si deseamos añadir la arista $(2,5)$ o $(1,3)$, en ambos casos los dos vértices que unen se encuentran en la misma componente conexa.
		Si consideramos la arista $(2,5)$ o $(1,3)$ para construir el árbol generador, estaríamos generando un ciclo en el grafo.

		\begin{figure}[!ht]
			\centerline{\includegraphics[scale=.5]{disjoint-graph1}}
			\caption{Arístas seleccionadas a partir de la utilización del \emph{disjoint-set} (azul)}
			\label{fig:disjointgraph1}
		\end{figure}

		El subgrafo resultante puede observarse en la imágen~\ref{fig:disjointgraph1}. Sólo las aristas que provocaron uniones de conjuntos fueron agregadas como parte de la solución en la construcción del árbol generador.

		En todo momento las aristas elegidas fueron las de menor peso posible, ya que se encontraban ordenadas. Con esto aseguramos que la suma del peso de las aristas sea mínimo.

	\newpage

	\subsubsection{Path-Compression}

		\emph{Path-Compression} es una heurística que permite obtener el conjunto al cual pertence un elemento en menor tiempo.

		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{example4a}
				\label{fig:example4a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{example4b}
				\label{fig:example4b}
			}
			\caption{Al buscar el conjunto al que pretenece el elemento $z$, path-compression transforma el árbol~\subref{fig:example4a} en ~\subref{fig:example4b}}
			\label{fig:example4}
		\end{figure}

		Cada vez que buscamos el conjunto al cual pertenece un elemento tenemos que recorrer el árbol hacia la raíz como se ve en la figura~\ref{fig:example4a}.
		Los nodos visitados para buscar el conjunto al cual pertenece el elemento $z$ son $V=\{z,y,x\}$, path-compression asigna a cada uno la raíz como su nuevo elemento padre (figura~\ref{fig:example4b}).
		De esta forma el árbol queda de menor altura y la próxima vez que se desee buscar el conjunto de cualquiera de los nodos en $V$, será inmediato.

	\subsubsection{Union-by-Rank}

		\emph{Union-by-rank} consiste en unir conjuntos teniendo en cuenta el tamaño (en altura) de cada uno.
		Al unir el conjunto $i$ con el $j$, si $altura(i)$ es mayor que $altura(j)$, la raíz del árbol del conjunto $j$ tendrá como padre a la raíz del conjunto $i$.
		La altura del árbol del conjunto $i$ tendrá ahora como altura (figura~\ref{fig:unionrank}):

		\begin{itemize}
				\item $altura(i) \leftrightarrow altura(i) > altura(j)$
				\item $altura(i)+1 \leftrightarrow altura(i) == altura(j)$
		\end{itemize}

		\begin{figure}[!ht]
			\centering
			\includegraphics[scale=.5]{unionrank}
			\caption{\emph{Union-by-Rank}}
			\label{fig:unionrank}
		\end{figure}

	\subsubsection{Análisis de Complejidad}

		Para realizar el análisis de complejidad definamos un grafo $G=(V,E)$ conexo, con $|V| = n$ (cantidad de servidores) y $|E| = m$ (cantidad de enlaces).
		Cómo $G$ es conexo la cantidad máxima de aristas que puede llegar a tener es la misma que un grafo completo, o sea $ m = \frac{n(n-1)}{2}$.
		Por eso acotaremos la cantidad de aristas por $\frac{n(n-1)}{2}$ para realizar las cuentas.

		Para obtener la entrada del algoritmo y almacenarla utilizamos un arreglo.
		Almacenar las aristas en el arreglo nos lleva $\mathcal{O}(m)$ operaciones, pero como lo acotamos por $\frac{n(n-1)}{2}$ nos queda $\mathcal{O}(n^2)$.

		El segundo paso es ordenar las aristas.
		Utilizando la función \emph{sort} de la librería estándar de \emph{C++}, nos lleva $\mathcal{O}(n^2\ log(n^2))$ operaciones.

		Crear un \emph{disjoint-set} lleva tiempo lineal en la cantidad de servidores, o sea $\mathcal{O}(n)$.
		Esto se debe a que se utiliza un arreglo como estructura de datos.

		Finalmente debemos realizar dos operaciones de \emph{find()} o búsqueda en el \emph{disjoint-set} seguido de una union, por cada arista de $G$.
		Las operaciones de búsqueda toman $\mathcal{O}(log(n))$ operaciones gracias a la implementación de las heurísticas mencionadas.
		La operación de union toma tiempo constante debido a que sólo debemos apuntar la raíz de un conjunto a la raíz de otro conjunto.
		Como resultado de iterar cantidad de aristas tenemos $\mathcal{O}(n^2\ log(n))$ operaciones.

		La complejidad total entonces será de:

		\begin{center}
			$\mathcal{O}(n^2) + \mathcal{O}(n) + \mathcal{O}(n^2 \ log(n^2)) + \mathcal{O}(n^2 \ log(n))$

			$\mathcal{O}(n^2) + \mathcal{O}(n) + \mathcal{O}(n^2 \ (log(n) + log(n))) + \mathcal{O}(n^2 \ log(n))$

			$\mathcal{O}(n^2) + \mathcal{O}(n) + \mathcal{O}(n^2 \ (log(n)) + \mathcal{O}(n^2 \ log(n))$

			$max\{ \mathcal{O}(n^2), \mathcal{O}(n), \mathcal{O}(n^2 \ log(n)), \mathcal{O}(n^2 \ log(n))\} = \mathcal{O}(n^2 \ log(n))$
		\end{center}

		Para realizar el análisis de complejidad se generaron grafos completos con distinto número de vértices.
		Luego se tomaron los tiempos de ejecución para cada parte del ejercicio (búsqueda de árbol generador mínimo y servidor maestro).
		Los tiempos se tomaron en nanosegundos. Cada instancia fue ejecutada un total de 1000 veces y luego el tiempo de ejecución resultante promediado para reducir el error de la medición.
		
		La razón de tomar grafos completos para efectuar las mediciones fue que el máximo número de aristas que puede procesarse para un grafo conexo de $n$ nodos es igual a las que posee un grafo completo.
		
		En la figura~\ref{fig:comparativaA} se ven los resultados de dicho experimento para la primera parte, encontrar el árbol generador mínimo.
		Los tiempos calculados se representan en una escala logarítmica (base 2) para que se puedan apreciar mejor los valores.
		Se puede apreciar como las heurísticas implementadas ayudan a reducir drásticamente los tiempos de ejecución del algoritmo.
		
		\begin{figure}[!ht]
			\centering
			\includegraphics[scale=.5]{comparativaAcompleto}
			\caption{Comparación entre la cota de complejidad calculada y el tiempo medido.}
			\label{fig:comparativaA}
		\end{figure}

	\newpage
	
	\subsection{Selección del servidor maestro}

		Todos los enlaces tardan el mismo tiempo en transmitir la información y el tiempo que cada servidor retiene el mensaje es despreciable.
		Sabiendo esto debemos elegir un servidor, de nuestro árbol generador mínimo, de forma tal que el tiempo de replicación del mensaje a toda la red sea mínimo.
		En otras palabras, queremos encontrar la raíz del árbol de manera tal que la altura sea mínima.
		
		Para esto vamos a utilizar un algoritmo que en cada paso va a podar todas las hojas del árbol, hasta llegar al caso base que consta de un solo nodo, o dos nodos adyacentes. Este caso base define el o los nodos centrales del árbol. A continuación se muestra el pseudocódigo del algoritmo seguido de un ejemplo gráfico de su comportamiento:

		\begin{itemize}
			\item Se genera una lista de adyacencias a partir de las aristas del árbol generador mínimo encontrado y se almacenan los grados de los nodos.
			\item Se inicializa una cola $C$.
			\item Por cada nodo $v$ del árbol generador mínimo.
			\begin{itemize}
				\item Si el grado de $v$ es 1 ($v$ es hoja) se añade a la cola $C$.
			\end{itemize}
			\item Mientras $C$ tenga al menos 1 elemento.
			\begin{itemize}
				\item Tomo un nodo hoja $h$ de $C$.
				\begin{itemize}
					\item Por cada nodo $i$ adyacente a $h$ (lista de adyacencias de $h$).
					\begin{itemize}
						\item Disminuyo el grado de $i$ en una unidad.
						\item Si $i$ se transforma en hoja al disminuir su grado, encolo $i$ en $C$.
					\end{itemize}
				\end{itemize}
			\end{itemize}
			\item Devuelvo como centro el último nodo que salió de $C$.
		\end{itemize}
		
		%~ \begin{itemize}
		 %~ \item Se agregan las hojas del árbol en una lista
		 %~ \item Se recorre la lista (mientras tenga algún elemento) y para cada hoja $n$:
			%~ \begin{itemize}
				%~ \item Se agregan sus nodos adyacentes en una lista
				%~ \item Se recorre la lista de adyacencias y para cada nodo:
				%~ \begin{itemize}
					%~ \item Si al sacarle a $n$ éste se transforma en hoja, lo agrego a la lista de hojas
				%~ \end{itemize}
				%~ \item Quito a $n$ de la lista de hojas
			%~ \end{itemize}
		%~ \end{itemize}

		\begin{center}
			\includegraphics[scale=0.45]{poda1.png}\\
			\vspace{1cm}
			\includegraphics[scale=0.45]{poda2.png}\\
			\vspace{1cm}
			\includegraphics[scale=0.45]{poda3.png}
		\end{center}		

		\vspace{0.5cm}
		
		¿Cómo podemos asegurar que este algoritmo es correcto y efectivamente devuelve el o los nodos centrales? 
		Para probar esto primero vamos a definir dos conceptos:
		
		\begin{center}
		Sea $T = (V,X)$ un árbol, definimos la \textbf{excentricidad} de $v \in V$ como: \\
		$exc(v) = max\{ min\{ camino(v,w) \} \forall w \in V \}$		
		\end{center}
		
		\begin{center}
		Sea $T = (V,X)$ un árbol, definimos el \textbf{centro de $T$} como el nodo $v \in V$ tal que al elegirlo como raíz, minimiza la altura de $T$. En otras palabras, $v$ es el centro de $T$ si y solo si $v$ es el nodo de menor excentricidad en $T$. \\
		\end{center}
		
		Además, vamos a enunciar y demostrar los siguientes lemas:\\
	
		\textbf{1)} Sea $T$ un árbol, y sea $T'$ el grafo obtenido luego de una poda de hojas de $T$. Entonces, $T'$ es árbol.\\		
		\textit{Demostración:} T es conexo y $m_{T} = n_{T} - 1$ por definición de árbol. Como es conexo, al eliminar una hoja, sigue siendo conexo, porque se elimina un nodo de grado 1 y nos aseguramos no formar otra componente conexa. Además, al borrar un nodo, también se borra una arista, por lo que se mantiene la diferencia de 1 en la cantidad de nodos y aristas. Entonces, T' es árbol. \\
		
		\textbf{2)} La excentricidad de un nodo $v$, va a estar definida por el camino mínimo de $v$ a alguna hoja.\\
		\textit{Demostración:} Supongamos que $exc(v)$ está definida por la distancia al nodo $w$. Supongamos además que $w$ no es una hoja. Entonces, $w$ tiene al menos dos nodos adyacentes. Llamémoslos $w_{1}$ y $w_{2}$. Podemos afirmar que el camino mínimo de $v$ a $w$ pasa por alguno de esos dos nodos, por ejemplo, $w_{1}$. Entonces, se podría extender el camino hasta $w_{2}$, y se obtendría un camino mínimo a $w_{2}$ cuya longitud es $1$ más que el camino mínimo a $w$. Esto significa que $w$ no es el máximo de los caminos mínimos, porque hay un camino mínimo a $w_{2}$ mayor, por lo que nunca pudo haber definido la excentricidad de $v$. 
		Este absurdo provino de suponer que $w$ no era hoja. \\
		
		\textbf{3)} Sea $T = (V,X)$ un árbol, y $T' = (V',X')$ el árbol obtenido luego de una poda de hojas de $T$. Entonces,
		\begin{center}
		$(\forall v \in V') exc_{T'}(v) = exc_{T}(v) - 1$.\\
		\end{center}
		\textit{Demostración:} Lo que queremos demostrar es que al realizar una poda, todas las excentricidades se reducen en una unidad. Si el nodo $v$ era una hoja en $T$, al realizar la poda fue eliminado, por lo que no se contempla su excentricidad. Si $v$ no era hoja, entonces su excentricidad está definida por el camino mínimo de $v$ a alguna hoja $w$ (por el lema 2). Veamos qué pasa si sacamos a $w$ del árbol. Llamemos $u$ al padre de $w$ en $T$. Supongamos que al sacar a $w$, $u$ quedó como un nodo con $d(u) \geq 2$ (no es una hoja). Esto significa que aparte de $w$ tenía más hijos. Si esos hijos eran hojas, tuvieron que haber sido podados. Si no eran hojas, y eran nodos padres, entonces el camino mínimo a $w$ no era el máximo, porque existiría un camino que pasa por $u$, su hijo que no es $w$, y su hijo; y sería al menos una unidad mayor. Esto es absurdo, y provino de suponer que $u$ no era una hoja. Por lo tanto, el camino mínimo que antes llegaba a $w$, y ahora llega a $u$, y será de longitud una unidad menor. Esto sucede para todos los caminos mínimos que llegaban a cada hoja, ya que siempre hablamos de un nodo $v$ genérico. Y además, al reducirse todos sus caminos mínimos en 1, la excentricidad va a estar definida por el mismo camino mínimo (aunque sin la hoja podada). Por lo tanto, la excentricidad de todos los nodos de T (que están en T') se reducen en una unidad.\\

		\vspace{0.5cm}
		Demostremos entonces por qué el algoritmo es correcto. Primero analicemos los casos base. Si un árbol tiene un solo nodo, trivialmente afirmamos que su centro es ese nodo. Si tiene dos nodos unidos por una arista, cualquiera puede ser centro, ya que la altura del árbol no se ve afectada por cuál nodo es la raíz. 
		
		Luego, lo que nos interesa saber es si el centro de un árbol $T$, es a su vez el centro de grafo $T'$ que se obtiene luego de la poda de hojas de $T$. Sabemos por el lema 1 que el grafo $T'$ es un árbol. Sabemos también por definición que el centro de un árbol es el nodo de menor excentricidad. Al realizar la poda, podemos afirmar que todas las excentricidades van a reducirse en una unidad (por el lema 3), por lo que el nodo de excentricidad mínima en $T$, va a ser el nodo de excentricidad mínima en $T'$, y por ende, va a ser el nodo central de $T'$.
		
		Finalmente, probamos que los casos base devuelven efectivamente el nodo central de un árbol, y que el paso recursivo mantiene el nodo central del árbol, por lo que podemos afirmar que el algoritmo es correcto.
		
		
	\subsubsection{Análisis de Complejidad}
		
		El primer paso es generar una lista de adyacencia utilizando las aristas del árbol generador mínimo obtenido del primer algoritmo.
		La lista de adyacencia está conformada por un arreglo de estructuras que representan a un vértice del grafo.
		Cada estructura vértice tiene un grado y una lista de índices que representan los nodos adyacentes.
		Si queremos procesar la arista $(x,y)$ debemos ir a la posición $x$ e $y$ respectivamente, aumentar el valor de sus grados y añadir a la lista de adyacentes a $y$ en el caso de $x$ y a $x$ en el caso de $y$.
		Ir a una posición dentro de un arreglo, aumentar el grado (operación con enteros) y añadir un elemento a una lista son operaciones que toman tiempo constante.
		Debido a lo anterior la complejidad para generar la lista de adyacencias tomará $\mathcal{O}(E)$, dónde $E$ es la cantidad de arístas.
		
		Ahora debemos crear una cola, que en definitiva es una lista enlazada, y recorrer la lista de vértices.
		Si tomamos un vértice de grado 1, debemos encolarlo a la cola anteriormente creada.
		Crear una cola nos lleva tiempo constante; e iterar sobre los vértices nos lleva $\mathcal{O}(V)$, dónde $V$ es la cantidad de vértices.
		
		Una vez que hicimos todo lo anterior nos queda empezar a quitar las hojas de la cola y recorrer los adyacentes de cada una, disminuyendo los grados y encolándo cada hoja nueva que se forme.
		Debido a el proceder del algoritmo, cada nodo de la lista se visita sólo una vez de la misma forma que los elementos de sus listas de adyacencia.
		Por ello el procedimiento es igual a el de recorrer la lista de adyacencia en cuanto a la complejidad requerida $\mathcal{O}(E+V)$.
		
		Finalmente nos queda como complejidad total:
		
		\begin{center}
			$\mathcal{O}(E) + \mathcal{O}(V) + \mathcal{O}(E+V)$
		\end{center}
		
		Notemos que como el grafo que estamos procesando es un árbol, entonces $E = V - 1$.
		Realizando el debido reemplazo y calculando la suma de las complejidades nos queda que el algortimo tiene una complejidad de $\mathcal{O}(V)$, donde $V$ es el número de servidores (vértices del árbol generador mínimo).
		
		En la figura~\ref{comparativaB}, se compara los tiempos medidos con la complejidad algorítmica calculada.
		El procedimiento para efectuar el cálculo fue idéntico al descripto para la primera parte del problema, buscar el árbol generado mínimo.
		El la imágen se observa que los tiempos medidos aumentan proporcionalmente con el tamaño de la entrada, de forma lineal.
		
		\begin{figure}[!ht]
			\centering
			\includegraphics[scale=.5]{comparativaB}
			\caption{Comparación entre la cota de complejidad calculada y el tiempo medido.}
			\label{fig:comparativaB}
		\end{figure}
		
	\subsection{Casos de prueba}
	
		El primer caso que analizaremos es el caso trivial, figura~\ref{fig:caso1}. Sólo tenemos 1 nodo en nuestra red de servidores y ningún enlace.
		Por lo tanto la solución deberá tener costo nulo y el único servidor existente será el maestro.
		En la imágen~\ref{fig:caso1a} puede observarse la descripción gráfica de los datos ingresados al programa.
		En la figura~\ref{fig:caso1b} se muestra el resultado dónde el nodo resaltado en rojo representa el servidor maestro determinado por nuestro algoritmo.
	
		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{caso-1}
				\label{fig:caso1a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{caso-1-resultado}
				\label{fig:caso1b}
			}
			\caption{Caso trivial.}
			\label{fig:caso1}
		\end{figure}
	
		El segundo caso consta de dos nodos unidos por una arista. En este caso la arista en cuestión es la única posible elección.
		Volvemos a presentar la entrada y la salida en el mismo formato anterior, figuras~\ref{fig:caso2a} y ~\ref{fig:caso2b}.
		En la imágen~\ref{fig:caso2b} se puede ver que los nodos y las aristas resaltados en verde/rojo son parte de la solución del algortimo de Kruskal.
		En rojo, también, se destaca el nodo que representa al servidor maestro.
		Tanto el nodo $1$ y $2$ son centros del grafo, a pesar de esto el programa sólo devuelve uno de ellos.
	
		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{caso-2}
				\label{fig:caso2a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{caso-2-resultado}
				\label{fig:caso2b}
			}
			\caption{Caso dos nodos unidos por una arista.}
			\label{fig:caso2}
		\end{figure}
		
		En el caso de la figura~\ref{fig:caso3}, se pueden observar 3 nodos unidos entre sí formando un ciclo.
		En este caso el algortimo podría habernos devuelto la arista $(2,3)$ en lugar de la $(1,2)$ ya que tiene mismo costo y también produce un árbol generador(el maestro pasaría a ser el servidor $3$).
		El vértice 1 fue elegido como maestro.
		
		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{caso-3}
				\label{fig:caso3a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{caso-3-resultado}
				\label{fig:caso3b}
			}
			\caption{Caso tres nodos unidos entre sí.}
			\label{fig:caso3}
		\end{figure}
		
		
		
		En el siguiente caso analizaremos que pasa cuando la estructura ya es un árbol en sí, figura~\ref{fig:caso4}.
		En este caso sólo existe una única solución en cuanto a encontrar el árbol generador mínimo.
		El servidor maestro fue bien elegido, el vértice $1$ es el elemento padre de todo el resto por lo que es la forma más rápida de transmisión posible.
		
		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{caso-4}
				\label{fig:caso4a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{caso-4-resultado}
				\label{fig:caso4b}
			}
			\caption{Caso árbol.}
			\label{fig:caso4}
		\end{figure}
		
		\newpage
		
		En la imágen~\ref{fig:caso6} tenemos una situación parecida, sólo que el árbol no está balanceado. Aún así puede verse que retorna el centro del mismo de forma correcta (en rojo).
		
		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{caso-6}
				\label{fig:caso6a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{caso-6-resultado}
				\label{fig:caso6b}
			}
			\caption{Caso árbol 2.}
			\label{fig:caso6}
		\end{figure}
		
		El último caso se trata de un grafo $K_{4}$. Sólo existe un árbol generador mínimo, el detectado por el programa (resaltado en verde).
		Si bien en este caso tanto el vértice $2$ como $4$ pueden ser posibles maestros, el programa devolvió el $2$ (en rojo).
				
		\begin{figure}[!ht]
			\centering
			\subfigure[]{
				\includegraphics[scale=.5]{caso-5}
				\label{fig:caso5a}
			}
			\subfigure[]{
				\includegraphics[scale=.5]{caso-5-resultado}
				\label{fig:caso5b}
			}
			\caption{Caso grafo $K_{4}$.}
			\label{fig:caso5}
		\end{figure}

\subsection{Pregunta Adicional 1}

	\begin{center}
	\includegraphics[scale=.4]{extra1.png}
	\end{center}
	
	En la figura superior, podemos observar un contra ejemplo de una solución óptima encontrada por Kruskal que no aplica como solución óptima del problema de manera integral.
	Esto sucede porque puede llegar a existir más de un árbol generador mínimo y a priori Kruskal no tiene un criterio para identificar la solución óptima dentro de éstos.
	
	Una forma de resolver el problema, es dotando al algoritmo de Kruskal de un criterio que permita hacer una evaluación de los distintos árboles generadores mínimos que puedan llegar a existir.
	Lo que queremos conseguir es que el árbol generador mínimo tenga la menor cantidad de niveles posible. De esta manera el broadcast (que avanza de nivel en nivel del árbol partiendo de la raíz que es el master) llega en menor tiempo.
	
	Una idea sobre como encarar la elección de este criterio puede llegar a ser que para las aristas que tienen igual peso, Kruskal determine un segundo orden priorizando aquellas que incidan en algún nodo de mayor grado que el resto (en el grafo original) y que ya tenga más aristas asignadas (en el grafo resultante).
	
\subsection{Pregunta Adicional 2}

Entendemos por multicast el hecho de que transmitir n mensajes por un enlace cueste lo que cuesta transmitir un mensaje multiplicado por n. A su vez, como los servidores que no son masters no pueden hacer copias, el master debe mandar tantos mensajes como descendientes tenga el nodo hijo al que le está mandando los paquetes. La figura a continuación muestra el costo de mandar un mensaje del master 1 al servidor 2 y 3.

\begin{center}
\includegraphics[scale=.7]{pregadic1.png}
\end{center}

Este escenario hace que cambie el costo de enviar un mensaje según la distancia que tengan los servidores respecto del master y no sólo respecto al costo de los enlaces. Por lo tanto, no hay ninguna garantía de que Kruskal (que minimiza el costo de los enlaces) me garantice una solución óptima.

\begin{center}
\includegraphics[scale=.7]{pregadic2.png}
\end{center}

Si aplicamos Kruskal al siguiente ejemplo, la arista (2, 3) se encontraría dentro de la solución. Sin embargo, al elegir como master al nodo 1, el costo de ir hasta el nodo 3 pasando por el 2 sería 5 (mandar dos paquetes al nodo 2 con costo 4 y que luego el nodo 2 mande uno de esos paquetes al nodo 3 con costo 1). En cambio, si hubieramos preservado las aristas (1, 3) y (1, 2) en vez de (2, 3) el costo de mandar los paquetes correspondientes a los nodos 2 y 3 sería en total de 4 (costo 2 para el nodo 2 y costo 2 para el nodo 3).

Por lo tanto, debemos descartar a Kruskal como una posible solución a la hora de elegir los enlaces. Una posible solución alternativa sería utilizar el algoritmo de Floyd para calcular el camino mínimo entre todos los nodos. Sabiendo el camino mínimo entre todos los nodos, quiero saber entonces cuál es el candidato idóneo para ser el master. Para esto, calculo para cada nodo, la suma de todos los caminos mínimos hacia el resto de los nodos. Voy a elegir como master al nodo cuya suma de todos los caminos mínimos sea menor. La razón de esta elección es que en multicast, el master deberá emitir un paquete de datos para cada uno de los nodos y enviarselo. Finalmente, cada paquete de datos deberá recorrer el camino desde el master hasta cada uno de los nodos. Por lo tanto, el nodo cuya suma de los caminos mínimos sea mínima, será el nodo capaz de enviar la totalidad de estos paquetes en menor tiempo. Los enlaces elegidos, además, serán aquellos que me permitan completar esos caminos mínimos entre el master y cada uno de los nodos.

Como dato adicional, esta solución tiene una complejidad del orden de $N^3$, ya que implica correr el algoritmo de Floyd-Warshall (del orden de $N^3$). Las operaciones que realiza luego (sumar para cada nodo el camino mínimo hacia el resto de los nodos, que ya tiene calculado) y elegir luego el mínimo entre estos valores son del orden de $N^2$ y $N$ respectivamente. Por lo tanto, la complejidad final es del orden de $O(N^3 + N^2 + N) = O(N^3)$

\subsection{Código Fuente}

Incluimos a continuación las funciones principales del código fuente de nuestro algoritmo:

\begin{verbatim}
void Consultant::solveA() {
    /* si no hay aristas salir, nada que hacer */
    if(edges.size() == 0)
        return;

    /* ordenar las aristas por costo */
    sort(edges.begin(), edges.end(), edgeCompare);

    /* Tomar las aristas más baratas y crear disjoint set */
    DisjointSet ds(node_count);

    for(vector< Edge >::const_iterator it = edges.begin(); it != edges.end(); it++) {
        if(ds.join(ds.find(it->x), ds.find(it->y))) {
            solution.push_back(*it);
            solution_cost += it->cost;
        }
    }
}

void Consultant::solveB() {
    if(edges.size() == 0)
        return;

    Node *nodes = new Node[node_count]; // O(vertices)

    for(int i = 0; i < node_count; i++) // O(vertices) {
        nodes[i].degree = 0;
    }

    /* crear lista de adyacencias */
    for(list< Edge >::const_iterator it = solution.begin(); it != solution.end(); it++) {
        nodes[it->x].adjacency.push_back(it->y);
        nodes[it->y].adjacency.push_back(it->x);
        nodes[it->x].degree++;
        nodes[it->y].degree++;
    }

    queue< int > leafs;

    for(int i = 0; i < node_count; i++) // O(aristas) {
        if(nodes[i].degree == 1)
            leafs.push(i);
    }

    int last = 0;

    while(leafs.size() > 0) // O(vertices) {
        /* tomo una hoja */
        last = leafs.front();

        /* disminuyo grado */
        nodes[last].degree--;

        /* disminuyo grado de sus adyacentes */

        for(list< int >::const_iterator it = nodes[last].adjacency.begin(); 
        it != nodes[last].adjacency.end(); it++) {
            nodes[*it].degree--;

            /* si se transforma en hoja la agrego a leafs */
            if(nodes[*it].degree == 1)
                leafs.push(*it);
        }

        /* quito la hoja */
        leafs.pop();    
    }

    /* el último nodo que queda es el master */
    master = last+1;

    delete[] nodes;
}
\end{verbatim}

